﻿using System;
using System.Collections.Generic;
using System.Text;

namespace ZackFlame.SimpleBrainFuck
{
    internal static class MathHelper
    {
        /// <summary>
        /// Разложение числа на множители алгоритмом Ферма.
        /// </summary>
        /// <param name="n">Разлагаемое число.</param>
        /// <returns>Можители числа.</returns>
        public static int[] Factorization(int n)
        {
            short i_max = (short)Math.Floor(Math.Log(n, 2)); // Максимальное кол-во множителей
            int[] factors = new Int32[i_max + 1];            // Массив в который будут писацца множители
            int next = 1;                                    // Следующий индекс массива

            factors[0] = n;
            int i = 0;
            bool exit = false;

            while (!exit)
            {
                factors[next] = FermatsMethod(ref factors[i]);

                if (factors[next] != 0) // Если разложилось, то
                    next++;             // пробуем разложить число на том же индексе
                else                    // Если число простое, то можно брать следующее
                    if (++i == i_max)   // Если весь массив "заполнен", то выходим
                        exit = true;
            }
            int newSize = 0;
            for (; newSize == 0; i--)                   // Уменьшаем индекс, как только найдем ненулевой
                if (factors[i] != 0) newSize = i + 1;   // элемент пербор будет закончен

            Array.Resize<int>(ref factors, newSize);    // Обрезаем нули
            Array.Sort(factors);                        // Сортируем в порядке возрастания
            return factors;
        }

        /// <summary>
        /// Метод Ферма для разложения числа на два простых сомножителя.
        /// </summary>
        /// <param name="n">Число для разложения и затем сомножитель.</param>
        /// <returns>Первый сомножитель.</returns>
        private static int FermatsMethod(ref int n)
        {
            if (n <= 2)
                return 0;
            
            if (n % 2 == 0) // Проверка на четность
            {
                n = n / 2;
                return 2;
            }
            
            int x = 1 + 2 * Convert.ToInt32(Math.Floor(Math.Sqrt(n)));
            int y = 1;
            int r = Convert.ToInt32(Math.Pow(Math.Floor(Math.Sqrt(n)), 2)) - n;
            int q = n / 2;

            bool exit = false;
            byte state = 2;
            while (!exit)
            {
                switch (state)
                {
                    case 2:
                        if (r <= 0)
                            state = 4;
                        else
                            state = 3;
                        break;
                    case 3:
                        r -= y;
                        y += 2;
                        if (y > q)
                            return 0;   // Возвращаем ноль, если число простое.
                        else
                            state = 2;
                        break;
                    case 4:
                        if (r == 0)
                            exit = true; // Найдены сомножители!
                        else
                        {
                            r += x;
                            x += 2;
                            state = 3;
                        }
                        break;
                }
            }

            // Возвращаем первый сомножитель, а через ссылку второй.
            n = (x - y) / 2;
            return (x + y - 2) / 2;
        }
    }
}
